package com.example.demo.calc;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @desc: <br/>
 * @author: Jingbo Hu<br/>
 * @time：2021年06⽉02⽇<br/>
 * @version：v1.0.0<br>
 */
public class BinaryTree3 {

    /**
     * 二叉树节点
     */
    public static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * 利用层序进行遍历
     * @param root 二叉树根节点
     */
    public static void levelOrderTraverse(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.data);
            if (node.leftChild != null){
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null){
                queue.offer(node.rightChild);
            }
        }
    }

    /**
     * 构建二叉树
     *
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        Integer data = inputList.removeFirst();
        // 这里的判断很关键，如果为空，则不再进行下一步
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    public static void main(String[] args) {
        Integer[] integers = {1, 2, 4, null, null, 5, null, null, 3, null, 6};
        LinkedList<Integer> inputList = new LinkedList<>();
        Arrays.stream(integers).forEach(arr -> {
            inputList.add(arr);
        });
        TreeNode binaryTree = createBinaryTree(inputList);
        levelOrderTraverse(binaryTree);
    }
}
